-- PrimeNumbers.hs

factors :: (Integral a) => a -> [a]
factors n = [x | x <- [1 .. n], mod n x == 0]

isPrime :: (Integral a) => a -> Bool
isPrime n = factors n == [1, n]

primes :: (Integral a) => a -> [a]
primes n = [x | x <- [1 .. n], isPrime x]

-- 提高素数的生成效率
isPrime2 :: (Integral a) => a -> Bool
isPrime2 2 = True
isPrime2 p = not (even p) && (all (\n -> p `mod` n /= 0) $ takeWhile (\n -> n * n <= p) [3, 5 ..])

primes2 :: (Integral a) => a -> [a]
primes2 n = [x | x <- [1 .. n], isPrime2 x]

-- 生成素数，从给定的 seed
nextPrime :: Integer -> Integer
nextPrime a
  | odd a && isPrime a = a
  | odd a = nextPrime (a + 2)
  | otherwise = nextPrime (a + 1)

-- 打印运行时间
-- :set +s
------------------------------------------- 埃拉托斯特尼筛法（Eratosthenes sieve）
sieve:: (Integral a) => [a] -> [a]
sieve (p:xs) = p : sieve [x| x <- xs, x `mod` p /=0]
sieve [] = []
primes3 n= sieve [2..n]

